package tech.seedhk.util;

import java.io.Serializable;
import java.util.*;


/**
 * @author zcy
 * @date 2019年7月3日 下午2:13:46
*/
public class BitTree implements Serializable{


	
	private static final  int ADDRESS_BITS_PER_WORD = 6;
    private static final  int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
    private static final long serialVersionUID = -8543323619769884829L;
    private static final long WORD_MASK = 0xffffffffffffffffL;

    private long[] words;
	
	private transient int wordsInUse = 0;

	private BitTree[] nextNodes;

    private int size;//BitTree 的大小

    private int depth;//当前节点的深度，从0开始(无用)


	public BitTree() {
        initWords(BITS_PER_WORD);
    }
	
	public BitTree(int nbits) {
        // nbits can't be negative; size 0 is OK
        if (nbits < 0){
            throw new NegativeArraySizeException("nbits < 0: " + nbits);
        }

        initWords(nbits);
	 }

    public void set(String str){
	    if(null==str || "".equals(str)){
	        throw new NullPointerException("str is null");
        }
        char[] chars=str.toCharArray();
	    //顶节点处理
        boolean b=this.get(chars[0]);
        if(!b){
            //顶节点的该位置为空
            this.set(chars[0]-65);
        }
        BitTree node=this;
        int d=0;
	    for(int i=1;i<chars.length;i++){
            int c=chars[i]-65;
            int a=chars[i-1]-65;
            d++;
            node=this.set(c,a,node,d);
        }
    }
    private BitTree set(int c,int pre,BitTree parent,int depth){

        BitTree node=parent.nextNodes[pre];
        if(node==null){
            BitTree bitTree=new BitTree(size);
            bitTree.set(c);
            bitTree.setDepth(depth);
            parent.nextNodes[pre]=bitTree;
            return bitTree;
        }else {
            node.set(c);
            node.setDepth(depth);
        }
        return node;
    }

    public List<String> get(String str){
        if(null==str || "".equals(str)){
            throw new NullPointerException("str is null");
        }
        List<BitNodeRet> cList=new ArrayList<>();

        loop(this,cList);

        System.out.println(cList.toString());


        return null;
    }


    /**
     * 依次遍历bit树，取出所有节点
     * @param node
     */
    private void loop(BitTree node,List<BitNodeRet> list){
        int[] arr=foreach(node);
        if(arr.length==0){
            return;
        }
        for(int i=0;i<arr.length;i++){
            int v=arr[i];//ascii值
            if(v==0){
                continue;
            }
            BitTree bNode=node.nextNodes[i];
            loop(bNode,list);
            BitNodeRet bitNodeRet =new BitNodeRet((char)(v+64),bNode,node.depth);//v+64=(v-1)+65
            list.add(bitNodeRet);
        }
    }




    public void set(int bitIndex) {
        if (bitIndex < 0) {
        	throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
        }

        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);

        words[wordIndex] |= (1L << bitIndex); // Restores invariants

        checkInvariants();
    }
    
    public void set(int bitIndex,BitTree parent) {
    	if (bitIndex < 0) {
    		throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    	}
        
        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);

        words[wordIndex] |= (1L << bitIndex); // Restores invariants

        this.setNext(bitIndex,parent);
        
        checkInvariants();
    }
    
    private boolean get(char c) {
    	return get((int)c-65);
    }

    private boolean get(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        int wordIndex = wordIndex(bitIndex);
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }
    
    public BitTree getNext(char c) {
    	return getNext((int)c-65);
    }
    
   
    
    public BitTree getNext(int bitIndex) {
    	 if (bitIndex < 0)
             throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

         checkInvariants();
         int wordIndex = wordIndex(bitIndex);
         
         if((wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0)) {
        	 return nextNodes[bitIndex];
         }
         
    	return null;
    }
    /**
     * 判断哪些位置为1
     * @param bitTree
     * @return
     */
    public int[] foreach(BitTree bitTree) {
        if(null==bitTree){
            return new int[0];
        }
    	int[] array=new int[size];
    	int b=0;
    	for(long l:bitTree.words) {
    		for(int i=1;i<size;i++) {
    			if(((1L<<(i-1))&l)!=0){
    				array[b++]=i;
    			}else {
                    array[b++]=0;
                }
    		}
    	}
    	return array;
    }

    /**
     * BitTree大小
     * @return
     */
    public int size(){
        return size;
    }

    private void initNext(int length) {
    	nextNodes=new BitTree[length];
    }
    
    private void setNext(int bitIndex,BitTree node) {
    	//将自己存入父类的指定节点
        synchronized (this){
            node.nextNodes[bitIndex]=this;
        }
    }
     
    
    private void expandTo(int wordIndex) {
        int wordsRequired = wordIndex+1;
        if (wordsInUse < wordsRequired) {
            ensureCapacity(wordsRequired);
            wordsInUse = wordsRequired;
        }
    }
    
    private void ensureCapacity(int wordsRequired) {
        if (words.length < wordsRequired) {
            // Allocate larger of doubled size or required size
            int request = Math.max(2 * words.length, wordsRequired);
            words = Arrays.copyOf(words, request);
        }
    }
    
    private void checkInvariants() {
        assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
        assert(wordsInUse >= 0 && wordsInUse <= words.length);
        assert(wordsInUse == words.length || words[wordsInUse] == 0);
    }
    
    private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
        initNext(nbits);
        size=nbits;
    }
    
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }

    private void setDepth(int depth){
        this.depth=depth;
    }

    public int cardinality() {
        int sum = 0;
        for (int i = 0; i < wordsInUse; i++)
            sum += Long.bitCount(words[i]);
        return sum;
    }

    public int nextSetBit(int fromIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

        checkInvariants();

        int u = wordIndex(fromIndex);
        if (u >= wordsInUse)
            return -1;

        long word = words[u] & (WORD_MASK << fromIndex);

        while (true) {
            if (word != 0)
                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
            if (++u == wordsInUse)
                return -1;
            word = words[u];
        }
    }

    public int nextClearBit(int fromIndex) {
        // Neither spec nor implementation handle bitsets of maximal length.
        // See 4816253.
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

        checkInvariants();

        int u = wordIndex(fromIndex);
        if (u >= wordsInUse)
            return fromIndex;

        long word = ~words[u] & (WORD_MASK << fromIndex);

        while (true) {
            if (word != 0)
                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
            if (++u == wordsInUse)
                return wordsInUse * BITS_PER_WORD;
            word = ~words[u];
        }
    }

    public String toString() {
        checkInvariants();

        int numBits = (wordsInUse > 128) ?
                cardinality() : wordsInUse * BITS_PER_WORD;
        StringBuilder b = new StringBuilder(6*numBits + 2);
        b.append('{');

        int i = nextSetBit(0);
        if (i != -1) {
            b.append(i);
            while (true) {
                if (++i < 0) break;
                if ((i = nextSetBit(i)) < 0) break;
                int endOfRun = nextClearBit(i);
                do { b.append(", ").append(i); }
                while (++i != endOfRun);
            }
        }

        b.append('}');
        return b.toString();
    }
}
